package top.lcm668.study.oj.base.sortmethods;

/**
 * @author: Coder-Lcm
 * @date: 2021/10/5 7:52
 * 希尔排序
 */
public class ShellSort<T extends Comparable<T>> extends BaseSort<T> {

    @Override
    protected void sort(T[] arr, boolean isAsc) {
        int len = arr.length;
        // 增量
        int gap = len / 2;
        while (gap > 0) {
            for (int i = gap; i < len; i++) {
                for (int i1 = i; i1 >= gap; i1 -= gap) {
                    if (isAsc ? lessThan(arr[i1], arr[i1 -gap]) : largeThan(arr[i1], arr[i1 - gap])) {
                        swap(arr, i1, i1 - gap);
                    }
                }
            }
            gap /= 2;
        }
    }
}
